package leetcode_100;


public class SudokuSolver_37 {

	public static void main(String[] args) {
		char board[][]=new char[][] {
			{'5','3','.','.','7','.','.','.','.'},
			{'6','.','.','1','9','5','.','.','.'},
			{'.','9','8','.','.','.','.','6','.'},
			{'8','.','.','.','6','.','.','.','3'},
			{'4','.','.','8','.','3','.','.','1'},
			{'7','.','.','.','2','.','.','.','6'},
			{'.','6','.','.','.','.','2','8','.'},
			{'.','.','.','4','1','9','.','.','5'},
			{'.','.','.','.','8','.','.','7','9'}};
		solveSudoku(board);

	}
	public static void print(char[][] board) {
		for(int i=0;i<9;++i) {
			for(int j=0;j<9;++j) {
				System.out.print(board[i][j]+" ");
			}
			System.out.println();
		}		
	}
	
	public static void solveSudoku(char[][] board) {
       help(board,0,0,true);
    }
	
	public static void help(char[][] board,int i,int j,Boolean flag) {
		if(flag) {
			if(board[i][j]!='.') {//已经有字符了
				if(j==8&&i==8) {
					flag=false;
					print(board);
					return ;
				}
				if(j==8)
					help(board,i+1,0,flag);
				else
					help(board,i,j+1,flag);
			}
			else {
				int index=1;
				while(index<=9) {
					char now=(char) ('0'+index);
					board[i][j]=now;
					if(isValidSudoku(board,i,j)) {//可以放
						if(j==8&&i==8) {
							flag=false;
							print(board);
							return ;
						}
						if(j==8)
							help(board,i+1,0,flag);
						else
							help(board,i,j+1,flag);
					}
					if(flag) {
					board[i][j]='.';
					++index;
					}
				}
			}
		}
	}
	
	public static boolean isValidSudoku(char[][] board,int i,int j) {
		if(!help(board, i, i+1, 0, 9))
			return false;
		else if(!help(board, 0, 9, j, j+1))
			return false;
		else if(i<3&&j<3) {
			if(!help(board, 0, 3, 0, 3))
				return false;
		}
		else if(i<3&&j>=3&&j<6) {
			if(!help(board, 0, 3, 3, 6))
				return false;
		}
		else if(i<3&&j>=6&&j<9) {
			if(!help(board, 0, 3, 6, 9))
				return false;
		}
		else if(i>=3&&i<6&&j<3) {
			if(!help(board, 3, 6, 0, 3))
				return false;
		}
		else if(i>=3&&i<6&&j>=3&&j<6) {
			if(!help(board, 3, 6, 3, 6))
				return false;
		}
		else if(i>=3&&i<6&&j>=6&&j<9) {
			if(!help(board, 3, 6, 3, 6))
				return false;
		}
		else if(i>=6&&i<9&&j<3) {
			if(!help(board, 6, 9, 0, 3))
				return false;
		}
		else if(i>=6&&i<9&&j>=3&&j<6) {
			if(!help(board, 6, 9, 3, 6))
				return false;
		}
		else if(i>=6&&i<9&&j>=6&&j<9) {
			if(!help(board, 6, 9, 6, 9))
				return false;
		}
		return true;
	}
	
	public static boolean help(char [][]board,int si,int ei,int sj,int ej) {
		
		boolean flags[]=new boolean[10];
		for(int i=si;i<ei;++i) {
			for(int j=sj;j<ej;++j) {
				if(board[i][j]=='.')
					continue;
				else {
					int index=board[i][j]-'0';
					if(flags[index]==true)
						return false;
					else 
						flags[index]=true;
				}
			}
		}	
		return true;
	}

	
}
